---
author: Marcus Rohrmoser
categories:
- en
- development
date: "2010-01-12T22:02:07+00:00"
tags:
- Binary
- Cocoa
- gist
- git
- github
- iPhone
- NSArray
- Objective C
- OS X
- Search
title: Binary Search NSArray
type: post
url: /2010/01/binary-search-nsarray/
yourls_shorturl:
- http://s.mro.name/3
---
Though [CFArray][1] comes with [binary search][2] capability, [NSArray][3] does not – at least not within the iPhone SDK. The [indexOfObject:inSortedRange:options:usingComparator:][4] can't be found.

Plus the [CFArrayBSearchValues][5] doesn't tell you whether the key actually is part of the list or not. That's what the [Java JDK][6] does, so let's implement some [category][7] methods

<pre class="line-numbers"><code class="language-objc">-(NSInteger)binarySearch:(id)key;
-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator;
-(NSInteger)binarySearch:(id)key usingSelector:(SEL)comparator inRange:(NSRange)range;
-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context;
-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context inRange:(NSRange)range;
-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors;
-(NSInteger)binarySearch:(id)key usingDescriptors:(NSArray *)sortDescriptors inRange:(NSRange)range;
</code></pre>

ourselves, like

<pre class="line-numbers"><code class="language-objc">-(NSInteger)binarySearch:(id)key usingFunction:(NSInteger (*)(id, id, void *))comparator context:(void *)context inRange:(NSRange)range
{
    NSLogD(@"[NSArray(MroBinarySearch) binarySearch:%@ usingFunction:]", key);
    if(self.count == 0 || key == nil || comparator == NULL)
        return [self binarySearch:key usingSelector:nil inRange:range];

//  check overflow?
    NSInteger min = range.location;
    NSInteger max = range.location + range.length - 1;

    while (min &lt;= max)
    {
        // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
        const NSInteger mid = min + (max - min) / 2;
        switch (comparator(key, [self objectAtIndex:mid], context))
        {
            case NSOrderedSame:
                return mid;
            case NSOrderedDescending:
                min = mid + 1;
                break;
            case NSOrderedAscending:
                max = mid - 1;
                break;
        }
    }
    return -(min + 1);
}
</code></pre>

See the [full interface + implementation + testcase without html encoding dirt at github][8].

 [1]: http://developer.apple.com/mac/library/DOCUMENTATION/CoreFoundation/Reference/CFArrayRef/index.html
 [2]: http://en.wikipedia.org/wiki/Binary_search_algorithm#Iterative
 [3]: http://developer.apple.com/mac/library/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html
 [4]: http://developer.apple.com/mac/library/documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html#//apple_ref/occ/instm/NSArray/indexOfObject:inSortedRange:options:usingComparator:
 [5]: http://developer.apple.com/mac/library/DOCUMENTATION/CoreFoundation/Reference/CFArrayRef/Reference/reference.html#//apple_ref/doc/uid/20001192-CH201-F10956
 [6]: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html#binarySearch(T[],%20T,%20java.util.Comparator)
 [7]: http://developer.apple.com/mac/library/documentation/General/Conceptual/DevPedia-CocoaCore/Category.html
 [8]: http://gist.github.com/275631/
